package leetcode_400;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 *@author 周杨
 *CountOfSmallerNumbersAfterSelf_315 给一个数组 返回一个数组 每个数组下标里存的数表示其右边有这么多数比它小
 *describe:用二叉搜索树 增加一个属性 判断其下有多少小于该节点 AC 76%  也可以用归并排序
 *2018年7月2日 下午8:06:23
 */
public class CountOfSmallerNumbersAfterSelf_315 {
	private class TreeNode {
        public int val;
        public int count = 1;
        public TreeNode left, right;
        
        public TreeNode(int val) {
            this.val = val;
        }
    }
	public static void main(String[] args) {
		CountOfSmallerNumbersAfterSelf_315 test=new CountOfSmallerNumbersAfterSelf_315();
		test.countSmaller(new int[] {5,2,6,1});

	}
	
	/**
	 * describe:用二叉搜索树 AC 76%
	 * 2018年7月2日 下午8:16:10
	 */
	public List<Integer> countSmaller(int[] nums) {
		List<Integer> res = new ArrayList<>();
        if(nums == null || nums.length == 0) {
            return res;
        }
        TreeNode root = new TreeNode(nums[nums.length - 1]);
        res.add(0);
        
        for(int i = nums.length - 2; i >= 0; i--) {
            int count = addNode(root, nums[i]);
            res.add(count);
        }
        
        Collections.reverse(res);
        return res;
    }
	
	 private int addNode(TreeNode root, int val) {
	        int curCount = 0;
	        while(true) {
	            if(val <= root.val) {
	                root.count++;                   // add the inversion count
	                if(root.left == null) {
	                    root.left = new TreeNode(val);
	                    break;
	                } else {
	                    root = root.left;
	                }
	            } else {
	                curCount += root.count;
	                if(root.right == null) {
	                    root.right = new TreeNode(val);
	                    break;
	                } else {
	                    root = root.right;
	                }
	            }
	        }
	        
	        return curCount;
	}
	 
	 /**
	 * describe:归并排序 AC 78%  归并排序每次可以确定这个元素有多少比它小
	 * 2018年7月2日 下午8:16:30
	 */
	public List<Integer> countSmaller1(int[] nums) {
	        int[] count = new int[nums.length];
	        int[] index = new int[nums.length];
	        for (int i = 0; i < nums.length; i++) index[i] = i;
	        mergeSort(nums, index, 0, nums.length, count);
	        List<Integer> list = new ArrayList<>();
	        for (int n : count) list.add(n);
	        return list;
	    }
	    private void mergeSort(int[] nums, int[] index, int lo, int hi, int[] count) {
	        if (lo > hi - 2) return;
	        int mid = (lo + hi) / 2;
	        mergeSort(nums, index, lo, mid, count);
	        mergeSort(nums, index, mid, hi, count);
	        int i = lo, j = mid, k = 0;
	        int[] arr = new int[hi - lo];
	        while (i < mid) {
	            while (j < hi && nums[index[j]] < nums[index[i]]) {
	                arr[k++] = index[j++];
	            }
	            count[index[i]] += k - (i - lo);
	            arr[k++] = index[i++];
	        }
	        for (i = 0; i < k; i++) index[i + lo] = arr[i];
	    }

}
